package com.heng.test;

import java.lang.String;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Demo {

    static class Edge {
        int v;
        int w;
        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public static void main(String[] args) {
        // 0 1 4
        // 0 2 6
        // 0 3 6
        // 1 2 1
        // 1 4 7
        // 2 4 6
        // 2 5 4
        // 3 2 2
        // 3 5 5
        // 4 6 6
        // 5 4 1
        // 5 6 8
        int n = 7;
        List<List<Edge>> e = new ArrayList<>();
        List<Edge> list0 = new ArrayList<>();
        list0.add(new Edge(1,4));
        list0.add(new Edge(2,6));
        list0.add(new Edge(3,6));
        e.add(list0);

        List<Edge> list1 = new ArrayList<>();
        list1.add(new Edge(2,1));
        list1.add(new Edge(4,7));
        e.add(list1);

        List<Edge> list2 = new ArrayList<>();
        list2.add(new Edge(4,6));
        list2.add(new Edge(5,4));
        e.add(list2);

        List<Edge> list3 = new ArrayList<>();
        list3.add(new Edge(2,2));
        list3.add(new Edge(5,5));
        e.add(list3);

        List<Edge> list4 = new ArrayList<>();
        list4.add(new Edge(6,6));
        e.add(list4);

        List<Edge> list5 = new ArrayList<>();
        list5.add(new Edge(4,1));
        list5.add(new Edge(6,8));
        e.add(list5);

        boolean[] vis = new boolean[n];
        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[0] = 0;

        // 迪杰斯特拉算法-单源最短路径
        for (int i = 0; i < e.size(); i++) {
            List<Edge> edges = e.get(i);
            vis[i] = true;

            for (Edge edge : edges) {
                dis[edge.v] = Math.min(edge.w + dis[i] , dis[edge.v]);
            }
            System.out.println(Arrays.toString(dis));
        }
        // 弗洛伊德算法-多源最短路径
    }


}
